决策树

决策树基本流程

核心思想

策略：分而治之

基本算法

自叶至根的递归过程在每个中间节点寻找一个划分属性 Pasted image 20240611205902.png

递归返回情况

节点内全部同为一类
- 节点类别标记为该类，作为一个叶节点
节点内还不完全是一类，但是已经没有属性可以用来划分了
- 节点类别标记为节点内占比最多的类，作为一个叶节点
节点内为空
- 节点标记为父节点内占比最多的类，作为一个叶节点

怎么选取划分属性？

1. 信息增益（ID3）

信息熵

还需要多少信息才能分开？

越接近0越纯净
越大越需要信息来分开
ID3划分标准：信息增益

用属性a对样本集及逆行划分所获得的信息增益

2. 增益率（C4.5 ）

限制一次不要生出太多树枝

IV(a)：体现用a属性作为分割会分出的树枝数量，体现a属性内的分裂程度，也称为属性a的固有值
C4.5 划分标准：增益率

3. 基尼系数(CART)

抽两个，不一样的概率

纯度：两个抽取的样本不一样的概率（越小越纯）
基尼系数：使用a属性划分之后的纯度

怎么防止过拟合？

剪枝

研究表明：划分选择的各种准则虽然对决策树的尺寸有较大影响，但是对泛化性能的影响很有限，而剪枝方法和程度对决策树泛化性能的影响更为显著！

判断剪枝前后泛化性能

模型评估方法
- 错误率
- 精度

预剪枝

通过判断划分前后整个树上对样本集的精度来决定是否剪枝
- 如果划分后精度下降或者精度不变(奥卡姆剃刀之树越简单越好)
  - 拒绝分裂（有欠拟合风险）
- 如果精度升高
  - 分裂

后剪枝

先构造整棵树，在从最深处开始剪枝（越深的分支越容易过拟合）
- 如果剪枝后精度下降或者精度不变（奥卡姆剃刀之步骤越少越好）
  - 保留
- 如果剪枝后精度上升
  - 剪枝

预剪枝VS后剪枝

预剪枝
- 测试时间开销降低，训练时间减少，欠拟合风险增加
后剪枝
- 测试时间开销降低，训练时间增加，欠拟合风险基本不变

怎么进行缺失值处理？

现实应用中，经常会遇到属性值缺失的现象，如果仅仅使用无缺失的样例值，就会损失掉那些有缺失值的数据里面蕴含的信息，造成对数据的极大浪费

要使用带缺失值的样例，需要解决如下问题

Q1：如何进行划分属性选择？

先只拿在该属性上有值的
- 然后增益率该咋算咋算
  - 最后在乘上一个有缺失值的样本数量除以全部样本数量的系数即可。
    - 最后把增益率最大的属性作为划分属性

Q2：给定划分属性，若样本在该属性上的值缺失，如何进行划分？

样本赋权，权重划分，同时进入

本质上是把样本进入各个分支的后验概率作为缺失值样本应该进入那个分支的先验概率。